0684. 冗余连接【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 并查集

1. 📝 题目描述

• leetcode

树可以看成是一个连通且 无环 的 无向 图。

给定一个图，该图从一棵 n 个节点 (节点值 1～n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

---

示例 1：

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

---

提示：

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• edges 中无重复元素
• 给定的图是连通的

2. 🎯 s.1 - 并查集

c

int parent[1001];
int rnk[1001];

int find(int x) {
    while (parent[x] != x) x = parent[x] = parent[parent[x]];
    return x;
}

int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    for (int i = 0; i <= edgesSize; i++) { parent[i] = i; rnk[i] = 0; }
    *returnSize = 2;
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        int pu = find(u), pv = find(v);
        if (pu == pv) {
            int* res = (int*)malloc(sizeof(int) * 2);
            res[0] = u; res[1] = v;
            return res;
        }
        if (rnk[pu] < rnk[pv]) parent[pu] = pv;
        else if (rnk[pu] > rnk[pv]) parent[pv] = pu;
        else { parent[pv] = pu; rnk[pu]++; }
    }
    *returnSize = 0;
    return NULL;
}

js

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
  const n = edges.length
  const parent = Array.from({ length: n + 1 }, (_, i) => i)
  const rank = new Array(n + 1).fill(0)
  const find = (x) => {
    while (parent[x] !== x) x = parent[x] = parent[parent[x]]
    return x
  }
  for (const [u, v] of edges) {
    const pu = find(u),
      pv = find(v)
    if (pu === pv) return [u, v]
    if (rank[pu] < rank[pv]) parent[pu] = pv
    else if (rank[pu] > rank[pv]) parent[pv] = pu
    else {
      parent[pv] = pu
      rank[pu]++
    }
  }
  return []
}

py

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))
        rank = [0] * (n + 1)
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for u, v in edges:
            pu, pv = find(u), find(v)
            if pu == pv:
                return [u, v]
            if rank[pu] < rank[pv]:
                parent[pu] = pv
            elif rank[pu] > rank[pv]:
                parent[pv] = pu
            else:
                parent[pv] = pu
                rank[pu] += 1
        return []

• 时间复杂度：$O(n\times \alpha (n))$，其中 $\alpha$ 是反阿克曼函数，近似 $O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 使用并查集，每次添加边时检查两端点是否已连通
• 若已连通则该边为冗余边，直接返回
• 使用路径压缩 + 按秩合并优化